INF = -1e7


class Solution(object):
    def find_max_x_sub(self, arr, lower, mid, upper):

        left_sum = INF
        cur_sum = 0
        i = mid
        while i >= lower:
            cur_sum += arr[i]
            if cur_sum > left_sum:
                left_sum = cur_sum
            i -= 1
 
        right_sum = INF
        cur_sum = 0
        i = mid + 1
        while i <= upper:
            cur_sum += arr[i]
            if cur_sum > right_sum:
                right_sum = cur_sum
            i += 1

        return left_sum + right_sum

    def find_max_sub(self, arr, lower, upper):
        if lower == upper:
            return arr[lower]
        else:
            mid = (lower + upper) / 2
            left_sum = self.find_max_sub(arr, lower, mid)
            right_sum = self.find_max_sub(arr, mid+1, upper)
            cross_sum = self.find_max_x_sub(arr, lower, mid, upper)

            return max([left_sum, right_sum, cross_sum])

    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return self.find_max_sub(nums, 0, len(nums)-1)

s = Solution()
r = s.maxSubArray([13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15])
print(r)
